package algorithm_diagram;

import java.util.Arrays;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;

//快速排序：类似二叉树方式进行排序，调用栈高度为LogN，每层需要时间为n，所以花费nLogN时间（在最糟情况下运行时间为n^2，但其遇上平均情况可能性要大得多）
// 随机选一个基准值，判断若满足基线条件（数组为空或只有一个元素）直接返回，若满足归纳条件则筛选出比基准值小相等与基准值大的数组，
// 然后对两组数组进行再排序直至满足基线条件。最后按照小与基准值数组，基准值，大于基准值数组的顺序排序。

//合并查找花费时间必然为nLogN，但是快速查找的常量比合并查找的常量小，所以在相同运行时间下，快速查找速度将更快
public class QuickSort {

    public static void main(String[] args) {
        System.out.println(quickSort01(Arrays.asList(54,23,13,15,12,5454,234,1235,234,676,453)));
    }

    private static List<Integer> quickSort01(List<Integer> list){//其速度取决于选择的基准值
        if(list.size()<2){
            return list;
        }else {
            Integer pivot = list.get(0);
            List<Integer> less = list.stream().skip(1).filter(element -> element <= pivot).collect(Collectors.toList());
            List<Integer> greater = list.stream().skip(1).filter(element -> element > pivot).collect(Collectors.toList());
            return Stream.of(
                    quickSort01(less).stream(),
                    Stream.of(pivot),
                    quickSort01(greater).stream())
                    .flatMap(Function.identity()).collect(Collectors.toList());
        }
    }
}
